#include <iostream>
#include <vector>

using namespace std;

// 检查在位置放置皇后是否安全
bool isSafe(const vector<vector<int>>& board, int row, int col, int n) {
	// 检查这一列是否有皇后
	for (int i = 0; i < row; ++i) {
		if (board[i][col] == 1) {
			return false;
		}
	}
	// 检查左上对角线是否有皇后
	for (int i = row, j = col; i >= 0 && j >= 0; --i, --j) {
		if (board[i][j] == 1) {
			return false;
		}
	}
	// 检查右上对角线是否有皇后
	for (int i = row, j = col; i >= 0 && j < n; --i, ++j) {
		if (board[i][j] == 1) {
			return false;
		}
	}
	return true;
}

bool solveNQUtil(vector<vector<int>>& board, int row, int n) {
	// 如果所有皇后都已成功放置
	if (row >= n) {
		return true;
	}
	for (int col = 0; col < n; ++col) {
		if (isSafe(board, row, col, n)) {
			// 放置皇后在当前位置
			board[row][col] = 1;
			// 递归放置其他皇后
			if (solveNQUtil(board, row + 1, n)) {
				return true;
			}
			// 如果放置失败，回溯
			board[row][col] = 0; 
		}
	}
	// 如果在当前行不能放置皇后，返回 false
	return false;
}

bool solveNQ(int n) {
	vector<vector<int>> board(n, vector<int>(n, 0));
	
	if (!solveNQUtil(board, 0, n)) {
		cout << "Solution does not exist" << endl;
		return false;
	}
	// 打印棋盘
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			cout << (board[i][j] ? "Q " : ". ");
		}
		cout << endl;
	}
	
	return true;
}
int main() {
	int n = 4;
	solveNQ(n);
	return 0;
}
